//你有一台电脑，它可以 同时 运行无数个任务。给你一个二维整数数组 tasks ，其中 tasks[i] = [starti, endi, 
//durationi] 表示第 i 个任务需要在 闭区间 时间段 [starti, endi] 内运行 durationi 个整数时间点（但不需要连续）。 
//
// 当电脑需要运行任务时，你可以打开电脑，如果空闲时，你可以将电脑关闭。 
//
// 请你返回完成所有任务的情况下，电脑最少需要运行多少秒。 
//
// 
//
// 示例 1： 
//
// 输入：tasks = [[2,3,1],[4,5,1],[1,5,2]]
//输出：2
//解释：
//- 第一个任务在闭区间 [2, 2] 运行。
//- 第二个任务在闭区间 [5, 5] 运行。
//- 第三个任务在闭区间 [2, 2] 和 [5, 5] 运行。
//电脑总共运行 2 个整数时间点。
// 
//
// 示例 2： 
//
// 输入：tasks = [[1,3,2],[2,5,3],[5,6,2]]
//输出：4
//解释：
//- 第一个任务在闭区间 [2, 3] 运行
//- 第二个任务在闭区间 [2, 3] 和 [5, 5] 运行。
//- 第三个任务在闭区间 [5, 6] 运行。
//电脑总共运行 4 个整数时间点。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= tasks.length <= 2000 
// tasks[i].length == 3 
// 1 <= starti, endi <= 2000 
// 1 <= durationi <= endi - starti + 1 
// 
//
// Related Topics 栈 贪心 数组 二分查找 排序 👍 54 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author ldltd
 * @date 2024-05-15 12:32:12
 * @description 2589.完成所有任务的最少时间
 */
public class MinimumTimeToCompleteAllTasks{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 MinimumTimeToCompleteAllTasks fun=new MinimumTimeToCompleteAllTasks();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*贪心+暴力
		 * 以结束时间从小到大排序，对每一个结束节点，
		 * 他的后一个节点要么和其没有交集，要么是他的一部分后缀
		 * 遍历数组，统计区间内已经运行的时间点，如果小于持续时间
		 * 尽量选择该区间后面的区间作为运行时间，
		 * 这样下个任务区间就可以尽可能的并行*/
    public int findMinimumTime1(int[][] tasks) {
		Arrays.sort(tasks,(a,b)->a[1]-b[1]);
		int res=0;
		//结束节点
		int mx=tasks[tasks.length-1][1];
		boolean [] vis =new boolean[mx+1];
		for (int[] t : tasks) {
			int l=t[0];
			int r=t[1];
			int d=t[2];
			for (int i = l; i <=r; i++) {
				if(vis[i]){
					d--;
				}
			}
			for (int i = r; d>0 ; i--) {
				if(!vis[i]){
					vis[i]=true;
					d--;
					res++;
				}
			}
		}
		return res;
    }
	/*栈+二分查找
	* 每次都是从右到左更新新增，可以看做
	* 与右侧区间合并成一一个大区间，可以用栈维护
	* 栈中存储左右端点，以及栈底到栈顶区间长度和
	* 如果新加入的相交就合并，则栈中都是不相交的
	* 合并前，现在栈中二分查找包含l的区间，
	* 由于栈中保存了区间长度，所以可以快速得到运行长度*/
	public int findMinimumTime(int[][] tasks) {
		Arrays.sort(tasks,(a,b)->a[1]-b[2]);
		//栈中保存区间左右端点和栈区间长度
		List<int []> st=new ArrayList<>();
		//哨兵，保证不和区间相交
		st.add(new int[]{-2,-2,0});
		for (int[] t : tasks) {
			int l=t[0],r=t[1],d=t[2];
			int []e=st.get(lowerBound(st,l)-1);
			//去掉运行中的时间点
			d-=st.get(st.size()-1)[2]-e[2];
			//如果l在区间st[i]中
			if(l<=e[1]){
				//去掉在运行中的节点
				d-=e[1]-l+1;
			}
			//如果已经够了，不合并直接跳过
			if(d<=0){
				continue;
			}
			//如果不够，需要合并区间到后缀
			//r-当前右端点满足时间要求
			while (r-st.get(st.size()-1)[1]<=d){
				//出栈
				e=st.remove(st.size()-1);
				//合并每段区间长度
				d+=e[1]-e[0]+1;
			}
			st.add(new int[]{r-d+1,r,st.get(st.size()-1)[2]+d});
		}
		return st.get(st.size()-1)[2];
	}
	public int lowerBound(List<int []>st,int k){
		//开区间（l,r)
		int l=-1,r=st.size();
		//区间不为空
		while (l+1<r){
			int m=(l+r)>>>1;
			if(st.get(m)[0]<k){
				l=m;
			}else {
				r=m;
			}
		}
		//或者l+1
		return r;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
